The subject invention pertains to the art of color image/text printing or display systems, and is especially applicable to a method and apparatus wherein color halftoning (representing a continuous tone image with a binary representation) is implemented with a partitioned stochastic screen or correlated stochastic screens for maximal ink dispersion and optimized spatial frequency response in the printing or display process.
In today""s business and scientific world color has become essential as a component of communication. Color facilitates the sharing of knowledge and ideas. Companies involved in the development of digital color print engines are continuously looking for ways to improve the accuracy and total image quality of their products.
Color images are commonly represented as one or more separations, each separation comprising a set of color density signals for a single primary or secondary color. Color density signals are commonly represented as digital gray or contone pixels, varying in magnitude from a minimum to a maximum, with a number of gradients between corresponding to the bit density of the system. Thus, a common 8 bit system provides 256 shades of each primary color. A color can therefore be considered the combination of magnitudes of each pixel, which when viewed together, present the combination color. Usually, printer signals include three subtractive primary color signals (Cyan, Magenta and Yellow) and a Black signal which together can be considered the printer colorant signals. Each color signal forms a separation and when combined together with the other separations, forms the color image.
Document Processing System devices (xe2x80x9cDPSxe2x80x9d) refers to a set of devices that construct, produce, print, transmit, scan, store and archive documents and their constituent elements. Such devices include marking engines, printers, scanners, fax machines, electronic libraries, and the like many of which can be employed in a xerographic environment. The present invention addresses situations particularly relevant to printing systems and discusses them as a prime example of a Document Processing System, but should not be construed to be limited to any such particular printing application. Any DPS is intended to benefit from the advantages of this invention.
Printers provide a limited number of output possibilities, and are commonly binary, i.e., they produce either a dot or no dot at a given pixel location. Thus, given a color separation with 256 shades of each additive primary color, a set of binary printer signals must be produced representing the contone effect. This process is referred to as halftoning. In such arrangements, over a given area and the separation having a number of contone pixels therein, each pixel value of an array of contone pixels within the area is compared to one of a set of preselected thresholds (the thresholds may be stored as a dither matrix and the repetitive pattern generated by this matrix is considered a halftone cell) as taught for example in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is a contone, some of the thresholds in the matrix will be exceeded, i.e., the image value at that specific location is larger than the value stored in the dither matrix for that same location, while others are not. In the binary case, the pixels or cell elements for which the thresholds are exceeded might be printed as black or some color, while the remaining elements are allowed to remain white or uncolored, dependent on the actual physical quantity described by the data. Since the human visual system tends to average out rapidly varying spatial patterns and perceives only a spatial average of the micro-variation in spot-color produced by a printer, the halftone process described above can be used to produce a close approximation to the desired color in the contone input.
The dither matrix of threshold values is often referred to as a xe2x80x9cscreenxe2x80x9d, and the process of generating the binary image from the contone image using the screen is called xe2x80x9cscreeningxe2x80x9d. Conventional digital halftones start as a number of isolated dots which grow bigger as more colorant is requested on the paper. These screens are referred to as clustered-dot screens. The fundamental rate at which the dots in a clustered dot screen are repeated is commonly referred to as the screen""s spatial frequency [Note R. Ulichney, xe2x80x9cDigital Halftoningxe2x80x9d, MIT Press, Cambridge, Mass., 1987]. The higher the screen spatial frequency, the finer and smoother appearing the image and also the greater is the capacity for the dots to represent fine detail in the image. Dithering creates problems in color document reproduction where the repeating pattern of a screen through the image, when superposed over similar repeating patterns in multiple separations, can cause moirxc3xa9 or other artifacts, particularly in a printing system with less than ideal registration between separations.
Stochastic, or non-periodic screening is an alternative to conventional clustered dot screens. Instead of producing dots that grow with increased colorant on paper, the stochastic screening method produces a well-dispersed pattern of isolated dots at spaced pixel locations. Thus there is no fundamental periodicity in the dots, instead the design of the screen attempts to produce patterns with pleasant noise characteristics. The pleasant noise characteristics are achieved by designing the screen so as to distribute the noise energy in the region of high spatial frequency, where the human visual system has a significantly reduced sensitivity. In this respect, U.S. Pat. No. 5,673,121 to Wang, discloses a stochastic halftone screening method for designing an idealized stochastic screen and is herein incorporated by reference as it discloses a particular stochastic screen useful in implementation of the subject invention, as will be more fully explained below. One of the advantages of stochastic, or non-periodic screening over periodic screening, is the suppression of moire.
Color stochastic screening has typically been implemented in the prior art by using the same screen for all separations (dot-on-dot) or by using independent screens (possibly obtained by shifting/rotating/flipping a single screen). These methods do not produce halftones with maximal ink dispersion and optimized spatial frequency response because there is no control of the overlap between the printed dots for different separations. The less successful the screening processes, the less smooth, i.e. more grainy, the resultant image appears. It is of course an overall objective of the subject invention to produce a resultant image in which the graininess is minimized, smoothness is enhanced and the intended colors are accurately reproduced.
One way to design and promote the desirable aspects of a single screen is through application and assessment of a xe2x80x9cmerit functionxe2x80x9d to the screen. Consider a halftone screen with N different threshold values, from 1 to N. The binary output B(x, y) is determined by the following dithering rule:
B(x,y)=1 if G(x,y)xe2x89xa7T(x,y);
B(x,y)=0 elsewherexe2x80x83xe2x80x83(1)
where x, y are the spatial coordinates, T is the threshold value at (x, y) and G is the gray-level input ranging from 0 to N. The value one of the output B represents a white pixel and zero, a black pixel. Without dot overlapping, a binary halftone pattern corresponding to a constant input level G will have G black pixels and Nxe2x88x92G white pixels within the area defined by the halftone screen. The visual appearance of this halftone pattern depends on whether the black pixels or the white pixels are minorities. If the white pixels are, i.e., G less than N/2, the appearance of the output should be based on the distribution of white pixels. Otherwise, the appearance should be on the distribution of black pixels. A merit function can be used to combine evaluations of all levels, thus, a half of the merit is on distributions of black pixels and another half is on white. The quantitative measure of visual evaluation on halftone outputs varies with specifications of the desired screens. For example, it is visually pleasant to have all minority pixels xe2x80x9cevenlyxe2x80x9d distributed on the output of a stochastic screen. Mathematically, it could be translated as maximizing the summation of all distances between any two minorities. In general, the contribution to the merit function from each gray level can be written as a function of the gray level and locations of all minorities appearing at this level. Since being minority or majority is determined by the dithering rule given by Eq. (1), in consequence, the contribution Q at level G can be written as a function of G and locations of corresponding thresholds in the halftone screen:
Q(G)=Q(G; x1, y1; x2, y2; . . . xG, yG), if G less than N/2
Q(G)=Q(G; xG+1, yG+1; xG+2, yG+2; . . . xN, yN) elsewhere, xe2x80x83xe2x80x83(2)
where xT, yT are coordinates of a threshold T.
The entire merit function M can be defined as a sum of contributions Q(G) from all levels:                               M          =                                    ∑                              G                =                0                            N                        ⁢                                          w                ⁡                                  (                  G                  )                                            ⁢                              Q                ⁡                                  (                  G                  )                                                                    ,                            (        3        )            
where w(G) is a weighting function of G. The objective of optimization is to maximize (or minimize) the single-value merit function M given above. Since the merit is used throughout the entire optimization process, the design can reach the best balance of all gray levels and the best compromise between given constraints in size, shape and other geometrical requirements.
Simulated annealing is a standard optimization technique and it has many different variations and modifications. It can be usefully applied to halftone screen design by analogizing the temperature to control the acceptance of a random swapping of screen threshold values in the iterative computing of the merit function to identify an optimized merit value. The acceptance is stochastically set by the temperature and compared with the change of the merit function due to swapping.
When the temperature is high, even a negative result could be accepted. So, the optimization would not easily fall into a local minimum. The temperature is gradually reduced during the optimization process and the final result is saved when the temperature drops to the low end. The flowchart of FIG. 1 demonstrates the basic optimization process for a single halftone screen design. At the beginning, all threshold values of the halftone screen are randomly set or copied from a previous design. The control temperature xcfx84 is set 20 to the starting temperature xcfx841. Whatever merit function is defined for the specific halftone screen is calculated 22.
The optimization loop begins with a random selection 24 of two threshold values, T1 and T2. After swapping the selected thresholds, the change of the merit function due to swapping is calculated 26. In general, the entire merit function M does not need to be recalculated, instead, only the contribution of levels between T1 and T2. If the change of the merit function meets 28 the acceptance set by the current temperature of simulated annealing, the swapped order is kept, the temperature xcfx84 is lowered 30, and the process proceeds 32 to the next swapping loop. Otherwise, the order is restored 34 before swapping and movement on to the next loop. This iteration process is continued until the temperature reaches 36 a desired low level xcfx840 and the final configuration of the screen is saved. Of course, if the result is not satisfactory, the temperature is reset and the optimization is started over again. For stochastic screens, it is possible to simplify Eq. (2), the merit function Q(G) at each gray level G, to a summation form:                                                                                           Q                  ⁡                                      (                    G                    )                                                  =                                                      ∑                                          i                      =                      l                                        G                                    ⁢                                                            ∑                                              j                        =                        1                                            G                                        ⁢                                          q                      ⁡                                              (                                                                              G                            ;                                                          x                              i                                                                                ,                                                                                    y                              i                                                        ;                                                          x                              j                                                                                ,                                                      y                            j                                                                          )                                                                                                        ,                                                                                            if                  ⁢                                      xe2x80x83                                    ⁢                  G                                 less than                                   N                  /                  2                                            ,                                                                                                            Q                  ⁡                                      (                    G                    )                                                  =                                                      ∑                                          i                      =                                              G                        +                        1                                                              N                                    ⁢                                                            ∑                                              j                        =                                                  G                          +                          1                                                                    N                                        ⁢                                          q                      ⁡                                              (                                                                              G                            ;                                                          x                              i                                                                                ,                                                                                    y                              i                                                        ;                                                          x                              j                                                                                ,                                                      y                            j                                                                          )                                                                                                        ,                                                          elsewhere              ,                                                          (        4        )            
where q only depends on G and locations of a pair of thresholds. Under such circumstances, calculation of the merit function could be reduced. For example, if both selected thresholds are less than the mean, i.e., T1 less than T2 less than N/2, the change of the merit function due to swapping, xcex94M, can be written as the following equation:                               Δ          ⁢                      xe2x80x83                    ⁢          M                =                              ∑                          G              =              T1                        T2                    ⁢                                    w              ⁡                              (                G                )                                      ⁢                                          ∑                                  i                  =                  1                                G                            ⁢                              [                                                      q                    ⁡                                          (                                                                        G                          ;                                                      x                            T2                                                                          ,                                                                              y                            T2                                                    ;                                                      x                            i                                                                          ,                                                  y                          i                                                                    )                                                        -                                      q                    ⁡                                          (                                                                        G                          ;                                                      x                            T1                                                                          ,                                                                              y                            T1                                                    ;                                                      x                            i                                                                          ,                                                  y                          i                                                                    )                                                                      ]                                                                        (        5        )            
An idealized stochastic screen would create such output patterns with any constant input G so that all minority pixels were xe2x80x9cevenlyxe2x80x9d separated. Mathematically, the above statement is equivalent to minimizing a merit function Q(G) given by Eq. (4), in which q(G; x1, y1, xj, yj) is a function of the distance between (xj, yj), or                               q          ⁡                      (                                          G                ;                                  x                  I                                            ,                                                y                  I                                ;                                  x                  j                                            ,                              y                j                                      )                          =                  1                                                    (                                                      x                    i                                    -                                      x                    j                                                  )                            2                        +                                          (                                                      y                    i                                    -                                      y                    j                                                  )                            2                                                          (        6        )            
A merit function M, given by Eq. (3), summarizes Q(G) of all levels with a chosen weighting function w(G) for example, defined by
w(G)=N/G, if G less than N/2;
w(g)=N/(Nxe2x88x92G), elsewhere.xe2x80x83xe2x80x83(7)
Using the defined merit function above, individual stochastic halftone screens can be designed in different sizes and shapes. Since a halftone screen is applied repetitively in the dithering process, additional consideration of the periodicity should be applied to the function q given by Eq. (6). As a matter of fact, if one utilizes a look-up table with pre-calculated function q between pixels, most calculation involved in the optimization is simple addition and the simulated annealing can proceed very quickly.
In accordance with the present invention, method and systems are provided for designing a plurality of correlated stochastic screens or conjugate screen portions intended for use in color halftoning of a corresponding plurality of color separations. A merit function is associated with each screen or screen portion. The merit function represents a measure of the desirability of the screen, particularly with regard to maximizing ink dispersion and optimizing spatial frequency response. An additional merit function is associated with the combination of the screens and screen portions. The additional merit function represents a measure of desirability of the screen combination with regard to ink dispersion and combined spatial frequency response. The screens are constructed so as to optimize the merit functions. The image is generated using the selected screens in a conventional color halftoning process with a plurality of color separations.
In one embodiment, the individual merit functions are combined into a single composite merit function using a weighted average and the screen construction process optimizes this composite merit function. Alternate, embodiments may utilize the individual merit functions in the screen construction process or may use forms of combination other than a simple weighted average.
The constructing of the plurality of screens preferably comprises an iterative process for optimizing the merit functions indicative of the desirability of each screen and the screen combination. The process starts with a random initial set of screens and iteratively modifies the screens for optimizing the chosen merit value or values. The merit functions are preferably based on placement of minority pixels for a plurality of tone and color values.
A principal advantage of the subject invention is a process for designing screens useful in color halftoning that achieve maximal ink dispersion and optimize the spatial frequency response in the imaging process.
Another advantage of the subject invention is a screen design process which facilitates screen design by assessing merit function values representative of maximal ink dispersion and optimized spatial frequency response through assessment of primary pixel locations.
Other objects and advantages will occur to others skilled in the art upon a reading and understanding of the present invention.